﻿using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;

namespace KnightTour
{
    public partial class KnightTour : Form
    {
        // 8 bước nhảy kế tiếp
        int[] x = { -2, -1, 1, 2, 2, 1, -1, -2 };
        int[] y = { 1, 2, 2, 1, -1, -2, -2, -1 };
        // Kích cỡ của bàn cờ
        const int intsize = 8;
        // Dùng để lưu những ô quân mã đã đi qua
        int[,] Board = new int[intsize, intsize];
        // Dùng để lưu số nước đi tại 1 ô
        int[,] CountMove = new int[intsize, intsize];
        int[] Temp = new int[8];
        // Kích cỡ 1 ô trên bàn cờ
        int intSizeCell = 75;
        // Dùng để lưu 2 màu Black,White
        ImageList ListChess = new ImageList();
        // Dùng để thoát đệ quy
        bool blnGo = false;
       
        // Dùng để xem bước đi kế tiếp của quân mã khi chạy chuong trình
        int intEnter = 0;

        int intRow = 0;
        int intColumn = 0;

        /**
         * Constructor
         */
        public KnightTour()
        {
            InitializeComponent();
            ListChess.Images.Add(Properties.Resources.Black);
            ListChess.Images.Add(Properties.Resources.White);
            ListChess.Images.Add(Properties.Resources.K3);
            DoubleBuffered = true;

           init();
           KnightGo(0, intRow, intColumn);
           
          
        }
        /**
         * Chuyển đổi giá trị 2 số
         */

        void Swap(ref int inta, ref int intb)
        {
            int intTemp;
            intTemp = inta;
            inta = intb;
            intb = intTemp;
        }

        /**
   		 * Kiểm tra xem nước đi có hợp lệ hay không
   		 */
                
        bool Check(int intNextCol, int intNextRow)
        {
            if (intNextCol > intsize - 1 || intNextCol < 0 || intNextRow > intsize - 1 || intNextRow < 0 || Board[intNextRow, intNextCol] != -1)
                return false;
            else return true;

        }
        /**
   		 * Dùng trong hàm Heuristics   
   		 */
     
        void Arrange(int intn, int intRow, int intCol)
        {
            int intCompareNextcol1;
            int intCompareNextrow1;
            int intCompareNextcol2;
            int intCompareNextrow2;

            for (int i = 0; i < intn; i++)
            {
                for (int j = i + 1; j < intn; j++)
                {
                    intCompareNextrow1 = intRow + x[Temp[i]];
                    intCompareNextcol1 = intCol + y[Temp[i]];
                    intCompareNextcol2 = intRow + x[Temp[j]];
                    intCompareNextrow2 = intCol + y[Temp[j]];
                    if (CountMove[intCompareNextrow1, intCompareNextcol1] > CountMove[intCompareNextrow2, intCompareNextcol2])
                        Swap(ref Temp[i], ref Temp[j]);
                }
            }

        }
        /**   		
         * Tính toán nước đi tối ưu
         */
        void Heuristic(int intRow, int intCol, ref int intStep)
        {
            int intNextcol;
            int intNextrow;

            intStep = 0;

        /**   		
   		 * Tính số nước đi có thể tại 1 vị trí trên bàn cờ
   		 */

            for (int i = 0; i < intsize; i++)
                for (int j = 0; j < intsize; j++)
                {
                    CountMove[i, j] = 0;
                    for (int k = 0; k < 8; k++)
                    {
                        intNextrow = i + x[k];
                        intNextcol = j + y[k];
                        if (Check(intNextcol, intNextrow))
                            CountMove[i, j]++;
                    }
                }

        /**
   		 * Lưu lại các vị trí có thể đi tiếp
   		 */

            for (int k = 0; k < 8; k++)
            {
                intNextrow = intRow + x[k];
                intNextcol = intCol + y[k];
                if (Check(intNextcol, intNextrow))
                {
                    Temp[intStep] = k;
                    intStep++;
                }

            }

        /**
   		 * Sắp xếp nước đi có thể với độ ưu tiên giảm dần
   		 */

            Arrange(intStep, intRow, intCol);

        }
        /**
         * Đệ quy để đi tiếp
         */
        void KnightGo(int intn, int intRow, int intColumn)
        {
            int intNextRow;
            int intNextCol;
            // Số nước có thể đi tại vị trí row,column
            int intStep = 0;
            // Đăt số thứ tự cho vi trí của quân mã đi vào
            Board[intRow, intColumn] = intn;
            
                if (intn >= intsize * intsize-1)
                {
                    // Đã đi hết bàn cờ thi thoát ra
                    blnGo = true;                  
                }
                else
                {
                    // Chọn ra nước đi tối ưu nhất
                    Heuristic(intRow, intColumn, ref intStep);

                    for (int i = 0; i < intStep; i++)
                    {
                        intNextRow = intRow + x[Temp[i]];
                        intNextCol = intColumn + y[Temp[i]];

                        if (Check(intNextCol, intNextRow))
                        {
                            /**
   		                     * Dùng đệ quy sang bước tiếp theo
   		                     */
                             KnightGo(intn + 1, intNextRow, intNextCol);
                        }

                    }
                }
              /**
	           * Nếu không thể đi tiếp và chưa đi hết thì vị trí này không có số thứ tự
	           */

           if (!blnGo)
                Board[intRow, intColumn] = -1;
        }

        /**
         * Khởi tạo bàn cờ
         */
        void init()
        {
            for (int i = 0; i < intsize; i++)
                for (int j = 0; j < intsize; j++)
                    Board[i, j] = -1;
        }
        /**
         * Tính toán vị trí của quân mã khi được click
         */
        private void KnightTour_MouseDown(object sender, MouseEventArgs e)
       {
           blnGo = false;
           intEnter = 0;
           intRow = e.X / intSizeCell;
           intColumn = e.Y / intSizeCell;
         
           init();
           KnightGo(0, intRow, intColumn);
           Invalidate();
       }
        /**
         * Vẽ bàn cờ,quân mã,số thứ tự
         */
        private void KnightTour_Paint(object sender, PaintEventArgs e)
        {
            

                for (int i = 0; i < intsize; i++)
                {
                    for (int j = 0; j < intsize; j++)
                    {
                        if ((i + j) % 2 != 0)
                            e.Graphics.DrawImage(ListChess.Images[0], i * intSizeCell, j * intSizeCell, intSizeCell, intSizeCell);
                        else
                            e.Graphics.DrawImage(ListChess.Images[1], i * intSizeCell, j * intSizeCell, intSizeCell, intSizeCell);
                        if (Board[i, j] == intEnter)
                        {
                            e.Graphics.DrawImage(ListChess.Images[2], i * intSizeCell, j * intSizeCell, intSizeCell, intSizeCell);
                        }
                        if (Board[i, j] < intEnter)
                        {
                            
                            Font drawFont = new Font("Arial", 30);
                            SolidBrush drawBrush = new SolidBrush(Color.Red);

                            PointF drawPoint = new PointF(i * intSizeCell + intSizeCell / 2 - 10, j * intSizeCell + intSizeCell / 2);
                            e.Graphics.DrawString((Board[i, j] + 1).ToString(), drawFont, drawBrush, drawPoint);
                        }
                    }
                }
              
           
        }
        /**
         * Hiển thị nước đi của quân mã khi nhấn enter
         */
        private void KnightTour_KeyDown(object sender, KeyEventArgs e)
        {
            if (e.KeyCode==Keys.Enter)
            {
                intEnter++;
            }
            Invalidate();
        }
        
       

              

       


        


       
    }
}
